#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/3/25 10:31
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 四数之和.py
# @Software: PyCharm

__author__ = 'yangdy'

from typing import List


class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        ans = []
        ll = len(nums)
        i = 0
        while i < ll - 3:
            if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
                break
            j = i + 1
            while j < ll - 2:
                if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:
                    break
                if nums[i] + nums[j] + nums[ll-2] + nums[ll-1] < target:
                    while j < ll - 2 and nums[j+1] == nums[j]:
                        j += 1
                    j += 1
                    continue
                k, l = j + 1, ll - 1
                while k < l:
                    e = nums[i] + nums[j] + nums[k] + nums[l]
                    if e == target:
                        ans.append([nums[i], nums[j], nums[k], nums[l]])
                        while k < l and nums[k + 1] == nums[k]:
                            k += 1
                        k += 1
                        while l > k and nums[l - 1] == nums[l]:
                            l -= 1
                        l -= 1
                    elif e > target:
                        while l > k and nums[l - 1] == nums[l]:
                            l -= 1
                        l -= 1
                    else:
                        while k < l and nums[k + 1] == nums[k]:
                            k += 1
                        k += 1
                while j < ll - 3 and nums[j + 1] == nums[j]:
                    j += 1
                j += 1
            while i < ll - 4 and nums[i + 1] == nums[i]:
                i += 1
            i += 1
        return ans


solve = Solution()
nums = [1, 0, -1, 0, -2, 2]
target = 0
print(nums, target)
print(solve.fourSum(nums, target))
